/*
 * @lc app=leetcode.cn id=981 lang=javascript
 *
 * [981] 基于时间的键值存储
 */

// @lc code=start
/**
 * Initialize your data structure here.
 */
var TimeMap = function() {
  this.map = new Map();
};

/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
  this.map.get(key) ? 
    this.map.get(key).push([value, timestamp]) :
      this.map.set(key, [[value, timestamp]]);
};

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
  if(!this.map.get(key)) return "";
  let values = this.map.get(key);
  let l = 0, r = values.length - 1;
  while(l < r){
    let mid = (l + r) >> 1;
    if(values[mid][1] < timestamp){
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  if(timestamp < values[r][1]) return r-1 >=0 ? values[r-1][0] : "";
  return values[r][0];
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */
// @lc code=end

